1877. Minimize Maximum Pair Sum in Array

Medium

題目描述

Description

The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

• For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.

Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

• Each element of nums is in exactly one pair, and
• The maximum pair sum is minimized.

Return the minimized maximum pair sum after optimally pairing up the elements.

Example 1:

Input: nums = [3,5,2,3]
Output: 7
Explanation:
The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

Example 2:

Input: n = [3,5,4,2,4,6]
Output: 8
Explanation:
The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

Constraints:

• n == nums.length
• 2 <= n <= 105
• n is even.
• 1 <= nums[i] <= 105

解答

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var minPairSum = function (nums) {
  nums.sort((a, b) => a - b);
  let left = 0;
  let right = nums.length - 1;
  let maxPairSum = 0;

  while (left < right) {
    const pairSum = nums[left] + nums[right];
    maxPairSum = Math.max(maxPairSum, pairSum);
    left++;
    right--;
  }

  return maxPairSum;
};

解題思路

根據這題的 Hint 1：Would sorting help find the optimal order? 以及題目的 Topics 裡面包含 Greedy 以及 Two Pointers，得知解題策略為先把 nums 升冪排序，再使用貪婪演算法逐步檢視每次最大和最小值的 Pair Sum，而要找最大和最小則使用 Two Pointers 的做法。

因為 nums.length 一定會是偶數所以也不用考慮奇數狀況。
每次算完 Pair Sum 後就更新目前的 maxPairSum，當 two pointer 結束後就是結果了

心得

讀懂題目比解題還難